<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
            读题：
            1. tickets是航线列表 tickets[i] = [fromi, toi] -> 从 fromi出发 到 toi降落
            2. 必须从 JFK出发
            3. 所有机票都必须用一次，且只能用一次
            4. 所有机票都至少存在一种合理的行程
            输入和输出
            1. 输入 [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
            输出 ["JFK","MUC","LHR","SFO","SJC"]
            2. 输入 [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
            输出 ["JFK","ATL","JFK","SFO","ATL","SFO"]

            问题：
            1. 不知道第一个字母该如何确认 出现了 ['JFK', 'SFO'] 和 ['JFK', 'ATL'] 该如何去抉择呢?
            2. 多种解法的时候，字母靠前的放前面，如何进行抉择呢？
            3. 本题要找到对数据进行排序，增删还不会让“容器”失效的
        */
        var findItinerary = function (tickets) {
            // part1
            debugger
            let result = ['JFK']
            let map = {}

            for (const ticket of tickets) {
                // part2
                /* 
                {
                    'JFK': undefined -> ['SFO'] -> ['SFO', 'ATL']
                }

                {
                    'JFK': undefined -> ['SFO'] -> ['SFO', 'ATL'],
                    'SFO': ['ATL'],
                }

                {
                    'JFK': undefined -> ['SFO'] -> ['SFO', 'ATL'],
                    'SFO': ['ATL'],
                    'ATL': ['JFK'] -> ['JFK', 'SFO']
                }
                */
                debugger
                const [from, to] = ticket
                if (!map[from]) {
                    map[from] = []
                }
                map[from].push(to)
            }

            // 对到达城市列表排序 为什么要排序 要把字母靠前的放前面 如果不排序怎么样呢
            for (const city in map) {
                /*  {
                     'JFK': undefined -> ['SFO'] -> ['SFO', 'ATL'],
                     'SFO': ['ATL'],
                     'ATL': ['JFK'] -> ['JFK', 'SFO']
                     ---->
                     'JFK': undefined -> ['SFO'] -> ['ATL', 'SFO'],这里变化了
                     'SFO': ['ATL'],
                     'ATL': ['JFK'] -> ['JFK', 'SFO']
                 } */
                // part3
                map[city].sort()
                /*  {
                  'JFK': undefined -> ['SFO'] -> ['SFO', 'ATL'] -> ['ATL', 'SFO']
                  'SFO': ['ATL'],
                  'ATL': ['JFK'] -> ['JFK', 'SFO']
                  ---->
                  'JFK': undefined -> ['SFO'] -> ['ATL', 'SFO'],这里变化了
                  'SFO': ['ATL'],
                  'ATL': ['JFK'] -> ['JFK', 'SFO']
              } */
            }

            // 
            function backtracking() {
                debugger
                // part4
                // 递归的退出条件
                if (result.length === (tickets.length + 1)) {
                    debugger
                    return result
                }
                // part5
                if (!map[result[result.length - 1]] || !map[result[result.length - 1]].length) {
                    // 表示 找不到下一个目的地了 出现了死循环
                    <debugger></debugger>
                    return false
                }

                // 
                for (let i = 0; i < map[result[result.length - 1]].length; i++) {
                    /* 
                        result[result.length - 1] -> JFK
                        i = 0, city = 'ALT'
                        map[JFK] -> ['ATL', 'SFO'],
                        splice 删掉'ALT', map[JFK] -> ['SFO'] 删掉了 下一回就不会再次放入
                        result.push(city) -> ['JFK', 'ALT']
                        进入下一波递归,backtracking()
                            i = 0
                            map[ALT] -> ['JFK', 'SFO'][0] -> 'JFK' city
                            splice 删掉'JFK' -> map[ALT] -> ['SFO'] 删掉了 下一回就再次放
                            result.push(city) ['JFK', 'ALT', 'JFK']
                            进入下一波递归，backtracking()
                                i = 0
                                map['JFK'] -> ['SFO'][0] -> 'SFO' city
                                splice 删掉 'SFO' -> map[JFK] -> []
                                result.push('SFO') ['JFK', 'ALT', 'JFK', 'SFO']
                                进入下一波递归，backtracking()
                                    i = 0
                                    map['SFO'] -> ['ALT'][0] -> 'ALT' city
                                    splice 删掉 'ALT' -> map[SFO] -> []
                                    result.push('SFO') ['JFK', 'ALT', 'JFK', 'SFO','ALT']
                                    进入下一波递归，backtracking()
                                        i = 0
                                        map['ALT'] -> ['SFO'][0] -> 'SFO' city
                                        splice 删掉 'SFO' -> map[ALT] -> []
                                        result.push('SFO') ['JFK', 'ALT', 'JFK', 'SFO','ALT', 'SFO']

                    */
                    debugger
                    // part6
                    let city = map[result[result.length - 1]][i]
                    // 删除已经走过的航线 防止死循环
                    map[result[result.length - 1]].splice(i, 1)
                    // 放到结果数组里面去
                    result.push(city)
                    // 
                    if (backtracking()) {
                        return true
                    }
                    result.pop()
                    map[result[result.length - 1]].splice(i, 0, city)
                }
            }
            backtracking()
            return result
        }
        console.log(findItinerary([["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]));
    </script>
</body>

</html>